#include <iostream>
using namespace std;
typedef struct {
    int x, y;
} ElemType;
typedef struct DuLNode { // 双向链表节点
    ElemType data;
    struct DuLNode *prior;  // 前驱指针
    struct DuLNode *next;   // 后继指针
} DuLNode, *DuLinkList;
void Init(DuLinkList &L) { // 初始化双向链表
    L = new DuLNode;
    L->prior = NULL;
    L->next = NULL;
}
bool IsEmpty(DuLinkList L) { // 判断链表是否为空
    return L->next == NULL;
}
void CreatFront(DuLinkList &L, int n) { // 头插法建立双向链表
    while(n--) {
        DuLNode *p = new DuLNode;
        cin >> p->data.x >> p->data.y;
        p->next = L->next;
        p->prior = L;
        if (L->next != NULL) {
            L->next->prior = p;
        }
        L->next = p;
    }
}
void CreatBack(DuLinkList &L, int n) { // 尾插法建立双向链表
    DuLNode *T = L;
    // 找到尾节点
    while (T->next != NULL) {
        T = T->next;
    }
    while(n--) {
        DuLNode *p = new DuLNode;
        cin >> p->data.x >> p->data.y;
        p->prior = T;
        p->next = NULL;
        T->next = p;
        T = p;
    }
}
void Get(DuLinkList L, int w, ElemType &e) { // 获取第w个元素的值
    if (IsEmpty(L)) return;
    DuLNode *p = L->next;
    int j = 1;
    while(p != NULL && j < w) {
        p = p->next;
        j++;
    }
    if(p == NULL || j > w) return;
    e = p->data;
}
DuLNode *Locate(DuLinkList L, ElemType e) { // 查找元素e的位置
    if (IsEmpty(L)) return NULL;
    DuLNode *p = L->next;
    while(p != NULL && (p->data.x != e.x || p->data.y != e.y)) {
        p = p->next;
    }
    return p;
}
void ShowForward(DuLinkList L) { // 输出双向链表（正向）
    if (IsEmpty(L)) {
        cout << "链表为空" << endl;
        return;
    }
    DuLNode *p = L->next;
    cout << "正向输出: ";
    while(p != NULL) {
        cout << "(" << p->data.x << "," << p->data.y << ")";
        if (p->next != NULL) {
            cout << " <-> ";
        }
        p = p->next;
    }
    cout << endl;
}
void ShowBackward(DuLinkList L) { // 输出双向链表（反向）
    if (IsEmpty(L)) {
        cout << "链表为空" << endl;
        return;
    }
    // 找到尾节点
    DuLNode *p = L->next;
    while(p->next != NULL) {
        p = p->next;
    }
    cout << "反向输出: ";
    while(p != L) {  // 一直回溯到头节点之前
        cout << "(" << p->data.x << "," << p->data.y << ")";
        if (p->prior != L) {
            cout << " <-> ";
        }
        p = p->prior;
    }
    cout << endl;
}
void Insert(DuLinkList &L, int w, ElemType e) { // 在第w个位置插入元素e
    DuLNode *p = L;
    int j = 0;
    // 找到第w-1个节点
    while(p != NULL && j < w-1) {
        p = p->next;
        j++;
    }
    if(p == NULL || j != w-1) return;  // 位置无效
    DuLNode *q = new DuLNode;
    q->data = e;
    // 调整四个指针
    q->prior = p;
    q->next = p->next;
    if (p->next != NULL) {
        p->next->prior = q;
    }
    p->next = q;
}
void Delete(DuLinkList &L, int w) { // 删除第w个元素
    if (IsEmpty(L)) return;
    DuLNode *p = L->next;
    int j = 1;
    // 找到第w个节点
    while(p != NULL && j < w) {
        p = p->next;
        j++;
    }
    if(p == NULL || j != w) return;  // 位置无效
    // 调整指针
    p->prior->next = p->next;
    if (p->next != NULL) {
        p->next->prior = p->prior;
    }
    delete p;
}
int Length(DuLinkList L) { // 获取链表长度
    int len = 0;
    DuLNode *p = L->next;
    while(p != NULL) {
        len++;
        p = p->next;
    }
    return len;
}
void Destroy(DuLinkList &L) { // 销毁双向链表
    DuLNode *p = L->next;
    while(p != NULL) {
        DuLNode *temp = p;
        p = p->next;
        delete temp;
    }
    delete L;
    L = NULL;
}
void InsertBefore(DuLNode *p, ElemType e) { // 在指定节点前插入
    if (p == NULL) return;
    DuLNode *q = new DuLNode;
    q->data = e;
    q->prior = p->prior;
    q->next = p;
    p->prior->next = q;
    p->prior = q;
}
void InsertAfter(DuLNode *p, ElemType e) { // 在指定节点后插入
    if (p == NULL) return;
    DuLNode *q = new DuLNode;
    q->data = e;
    q->prior = p;
    q->next = p->next;
    if (p->next != NULL) {
        p->next->prior = q;
    }
    p->next = q;
}
int main() {
    DuLinkList L;
    Init(L);
    int n;
    cin >> n;
    CreatBack(L, n);
    ShowForward(L);
    ShowBackward(L);
    // 测试插入
    ElemType e1 = {100, 200};
    Insert(L, 2, e1);
    cout << "在第2个位置插入(100,200)后:" << endl;
    ShowForward(L);
    // 测试删除
    Delete(L, 3);
    cout << "删除第3个节点后:" << endl;
    ShowForward(L);
    // 测试在指定位置前后插入
    DuLNode *found = Locate(L, e1);
    if (found != NULL) {
        ElemType e2 = {300, 400};
        InsertBefore(found, e2);
        cout << "在(100,200)前插入(300,400)后:" << endl;
        ShowForward(L);
        ElemType e3 = {500, 600};
        InsertAfter(found, e3);
        cout << "在(100,200)后插入(500,600)后:" << endl;
        ShowForward(L);
    }
    cout << "链表长度: " << Length(L) << endl;
    Destroy(L);
    return 0;
}